package leetcode.newVersion.twoPointers;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class lc15 {
    /*
    首先对数组进行排序，排序后固定一个数 nums[i]，再使用左右指针指向 nums[i]后面的两端，数字分别为 nums[L] 和 nums[R]，计算三个数的和 sum 判断是否满足为 0，满足则添加进结果集
    已经理解逻辑，但是代码实现部分还要再看看
     */
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();

        for(int i = 0; i <nums.length-2; i++){//注意i的边界条件，只需要到倒数第三个即可。后面两个元素是lN和rN，不需要遍历
            // 跳过重复的固定元素
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int head = nums[i];
            int left=i+1;
            int right=nums.length-1;


            while (left<right){
                int leftNum = nums[left];
                int rightNum = nums[right];
                int sum = head + leftNum + rightNum;

                if (sum == 0){
                    res.add(Arrays.asList(head,leftNum,rightNum));
                    right--;
                    left++;

                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    // 跳过右侧重复元素
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                }
                else if (sum > 0){//结果大于零，说明RN太大，将右指针向左移
                    right--;
                }else {//结果小于零，说明LN太小，将左指针向右移
                    left++;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        lc15 sol = new lc15();
        int[] nums = {-1,0,1,2,-1,-4};
        System.out.println(sol.threeSum(nums));
    }
}
